fixedpointfandomcom-20200213-history
Fixed Point Wiki
Fixed-Point Iteration In numerical analysis, fixed point iteration is a method of computing fixed points of iterated functions, which is one of the fundamental functions in computer science. As the name suggests, a process is repeated until an answer is achieved. Iterative techniques are used to find roots of equations, solutions of linear and nonlinear systems of equations, and solutions of differential equations. A number p is a fixed po'i'''nt '''for a given function ''g ''if ''g(p) = p. ''In this section we consider the problem of finding. : : Let 'Φ'be a continuous function and {''Xn ''} the sequence generated by : ''Xn+1 ''= 'Φ{' 'Xn ''}, n = 0, 1, 2, . . . (fig. 1) : i.e., the limiting value ''α''' is a root of the equation'' 'x = Φ{x},'' ''We call 'α' or a fixed point''' of the mapping '''x ''-> Φ{ ''x } '''and the iteration (fig. 1) a fixed-point iteration. 'Fixed Point Algorithm ' Input: X0, TOL, N0 Output: X'' or message of failure Step 1: Set ''i = 1 ''Step 2: While ''i ≤ N0 do Steps 3 - 6 '' Step 3: Set ''X = g(X0) % Compute Xi Step 4: if |X – X0| < TOL then Output (X); % found not Stop Step 5: Set i = i + 1 ''Step 6: Set ''X0 = X. ''Update ''X. Step 7: Output (Iterations exceeded.'' N > N0'' ) END Example '''Example 1. Use fixed point iteration to find the fixed point(s) for the function . g(x) = 1 + x - ( x2 / 3 ) xn+1 = 1 + xn - (xn2 / 3 ) x0= 3.000000 x1 = 1.000000 x2= 1.666667 x3= 1.740740 x4= 1.730681 x5 = 1.732262 x6= 1.732018 x7= 1.732056 Usually, you can iterate over and over again, until there is not much difference between the present and previous values.Using the example above, 10 iterations can satisfy the difference mentioned above. x0= 3.000000 x1 = 1.000000 x2= 1.666667 x3= 1.740740 x4= 1.730681 x5 = 1.732262 x6= 1.732018 x7= 1.732056 x8 = 1.732050 x9= 1.732051 x10= 1.732051 But it still depends on what your target is, say 10 iterations for this example. A tolerance value may also be used as basis for stopping the iteration. Applications Newton's method for a given differentiable function f(x) is . If we write we may rewrite the Newton iteration as the fixed point iteration xn + 1 = g(xn). If this iteration converges to a fixed point x of g then so . The inverse of anything is nonzero, therefore f(x) = 0: x is a root of f. Assuming the hypotheses of the Banach fixed point theorem are satisfied, we have that the Newton iteration converges linearly. However, a more detailed analysis shows that under certain circumstances, . This is called quadratic convergence. Runge-Kutta methods and numerical Ordinary Differential Equation solvers in general can be viewed as fixed point iterations. Indeed, the core idea when analyzing the A-stability of ODE solvers is to start with the special case y' = ay, where a is a complex number, and to check whether the ODE solver converges to the fixed point y = 0 whenever the real part of a is negative. Some of the "successive approximation" schemes used in dynamic programming to solve Bellman's functional equation are based on fixed point iterations in the space of the return function. Pseudo-code Tol := 0.000001 {Termination criterion} Max := 200 {Maximum number of iterations} Small := 0.000001 {Initialize the variable} K := 0 {Initialize the counter} RelErr := 1 {Initialize the variable} INPUT Pterm {The initial approximation} Pnew := g(Pterm) (The first iteration) WHILE RelErr >= Tol and K <= Max DO : K := K+1 {Increment the counter} : Pold := Pterm {Previous iterate } : Pterm := Pnew {Current iterate } : Pnew := g(Pterm) {Compute new iterate } : Dg := Pnew - Pterm {Difference in g(x)} : Delta := |Dg| {Absolute error} : RelErr := 2*Delta/(|Pnew|+Small) (Relative Error} END WHILE : Dx := Pterm - Pold {Difference in x} : Slope := Dg/Dx {g'(Pk)} PRINT "The computed fixed point of g(x) is " Pnew {Output} PRINT "Consecutive iterates are within " Delta IF |Slope| > 1 THEN : PRINT "The sequence appears to be diverging." ELSE : PRINT "The sequence appears to be converging." ENDIF Computer Program Codes Matlab Code function k,p,err,P = fixpt(g,p0,tol,max1) % Input - g is the iteration function % - p0 is the initial guess for the fixed-point % - tol is the tolerance % - max1 is the maximum number of iterations % Output - k is the number of iterations that were carried out % - p is the approximation to the fixed-point % - err is the error in the approximation % - P'contains the sequence {pn} P(1)= p0; for k=2:max1 : P(k)=feval(g,P(k-1)); : err=abs(P(k)-P(k-1)); : relerr=err/(abs(P(k))+eps); : p=P(k); : if (err #include #include /* define prototype for USER-SUPPLIED function g(x) */ : double gfunction(double x); /* EXAMPLE for "gfunction" */ : double gfunction(double x) : { :: return ( 1 + x - pow(x,2)/4 ); : } /* -------------------------------------------------------- */ /* Main program for algorithm 2.1 */ : void main() { :: double MaxPnew = 1E+200; /* highest absolute value for Pnew */ :: double Tol = 0.000001; /* Termination criterion */ :: int Max = 200; /* Maximum number of iterations */ :: double Small = 0.000001; /* Initialize the variable */ :: int K = 0; /* Initialize the counter */ :: double RelErr = 1; /* Initialize the variable */ :: double Pterm; /* INPUT : The initial approximation */ :: double Pnew; /* Result of a iteration */ :: double Pold,Dg,Delta,Dx,Slope; :: int iwarn = 0; /* Initialize warning flag */ :: printf("Please enter START-value for iteration :\n"); :: scanf("%lf", &Pterm); :: printf("START-value for iteration : Pterm = %lf\n", Pterm); :: printf(""); :: Pnew = gfunction(Pterm); /* First iteration */ : while( (RelErr >= Tol) && (K <= Max) ) { :: K++; /* Increment the counter */ :: Pold = Pterm; /* Previous iterate p_(k+1) */ :: Pterm = Pnew; /* Current iterate p_k */ :: Pnew = gfunction(Pterm); /* Compute new iterate p_(k+1) */ : if( fabs(Pnew) > MaxPnew){ /* Check for +/-INF before :: the end of the while-loop */ :: iwarn = 1; /* set flag for warning */ :: break; /* break out of while-loop */ : } :: Dg = Pnew - Pterm; /* Difference in gfunction */ :: Delta = fabs(Dg); /* Absolute Error */ ;: RelErr = 2 * Delta / ( fabs(Pnew) + Small ); /* Relative Error */ : } /* End of the 'while'-loop */ :: Dx = Pterm - Pold; /* Difference in x */ ;: Slope = Dg / Dx; /* g'(p_k) */ : printf("-----------------------------------------------\n"); : if(iwarn){ /* Tell that Pnew has grown dramatically and stop */ :: printf("Number of iterations : %d\n",K); :: printf("Iteration walks out of precision range !!\n"); :: printf("Value of x = Pnew = %G\n", Pnew); :: printf("The sequence appears to be diverging !\n"); :: exit(0); : } :: printf("Number of iterations : %d\n",K); :: printf("The computed fixed point of g(x) is %lf\n",Pnew); :: printf("Consecutive iterations are within %lf\n", Delta); : if( fabs(Slope) > 1 ) printf("The sequence appears to be diverging.\n"); : else printf("The sequence appears to be converging.\n"); } /* End Main Program */ BASIC Code :10 DEF FNF(X) = X*SIN(X) - 1 :15 GOTO 100 :20 PRINT"F(X) = X*SIN(X) - 1" :30 RETURN :100 REM PROGRAM BISECTON :110 DELTA=.0000005 :120 GOSUB 300: REM SUBROUTINE GETPOINTS :130 A1=A :140 B1=B :150 GOSUB 400: REM SUBROUTINE BISECTION :160 GOSUB 1000:REM SUBROUTINE RESULTS :170 PRINT :180 PRINT"WANT TO TRY ANOTHER INTERVAL? "; :190 INPUT ANS$ :200 IF ANS$ = "Y" OR ANS$ = "y" THEN GOTO 120 :210 GOTO 1460 :300 REM SUBROUTINE GETPOINTS :310 CLS :320 PRINT"THE BISECTION METHOD WILL BE USED TO FIND A ZERO THE FUNCTION" :330 PRINT :340 GOSUB 20: REM PRINT FUNCTION :350 PRINT :360 PRINT"THAT LIES IN THE INTERVAL A,B" :370 PRINT :380 PRINT"ENTER LEFT ENDPOINT A = "; :390 INPUT A :392 PRINT"ENTER RIGHT ENDPOINT B = "; :394 INPUT B :396 PRINT :398 RETURN :400 REM SUBROUTINE BISECTION :410 BIG=1E+10 :420 K=0 :430 KL=0 :440 KR=0 :450 YA=FNF(A) :460 YB=FNF(B) :470 D=B-A :480 COND=0 :490 MAX=1+INT((LOG(D)-LOG(DELTA))/LOG(2)) :500 IF YA*YB => 0 THEN COND=1: GOTO 770 :510 WHILE (COND=0) AND (K < MAX) :520 C=(A+B)/2 :530 YC=FNF© :540 IF YC = 0 THEN 550 ELSE 590 :550 A=C :560 B=C :570 COND=2 :580 GOTO 690 :590 REM ELSEIF :600 IF YB*YC > 0 THEN 610 ELSE 650 :610 B=C :620 YB=YC :630 KR=KR+1 :640 GOTO 690 :650 REM ELSE :660 A=C :670 YA=YC :680 KL=KL+1 :690 REM ENDIF :700 K=K+1 :710 WEND :720 D=B-A :730 IF D < DELTA THEN 740 ELSE 760 :740 IF COND <> 2 THEN COND=3 :750 IF ABS(YA) > BIG AND ABS(YB) > BIG THEN COND=4 :760 REM ENDIF :770 REM CONTINUE :780 RETURN :1000 REM SUBROUTINE RESULTS :1010 PRINT"THE BISECTION METHOD WAS USED TO FIND A ZERO OF THE FUNCTION" :1020 PRINT :1030 GOSUB 20: REM PRINT FUNCTION :1040 PRINT :1050 PRINT"IN THE INTERVAL ,",B," " :1060 PRINT :1070 K=KL+KR :1080 IF COND = 1 THEN 1090 ELSE 1170 :1090 PRINT"THE VALUES F(A) AND F(B)" :1100 PRINT"DO NOT DIFFER IN SIGN." :1110 PRINT :1120 PRINT"F(",A," ) =",FNF(A) :1130 PRINT"F(",B," ) =",FNF(B) :1140 PRINT :1150 PRINT"THE BISECTION METHOD CANNOT BE USED." :1160 GOTO 1430 :1170 REM ELSEIF :1180 IF COND = 2 OR COND = 3 THEN 1190 ELSE 1330 :1190 PRINT"THE BISECTION METHOD TOOK ",K," ITERATIONS." :1200 PRINT :1210 PRINT"THERE WERE",KR," SQUEEZES FROM THE RIGHT" :1220 PRINT :1230 PRINT" AND",KL," SQUEEZES FROM THE LEFT." :1240 PRINT :1250 PRINT" THE ROOT IS C =",C :1260 PRINT :1270 PRINT"THE ACCURACY IS +-",D :1280 PRINT :1290 PRINT"FUNCTION VALUE F(",C," ) =",FNF© :1300 PRINT :1310 IF COND = 2 THEN PRINT"THE FUNCTION VALUE IS EXACTLY ZERO!" :1320 GOTO 1430 :1330 REM ELSEIF :1340 IF COND = 0 OR COND = 4 THEN 1350 ELSE 1430 :1350 PRINT"THE CURRENT ITERATE IS C(",K,") =",C :1360 PRINT :1370 PRINT"THE CURRENT INTERVAL WIDTH IS ",D :1380 PRINT :1390 PRINT"THE CURRENT FUNCTION VALUE F(",C," ) =",FNF© :1400 PRINT :1410 IF COND = 0 THEN PRINT"THE MAXIMUM NUMBER OF ITERATIONS WAS EXCEEDED." :1420 IF COND = 4 THEN PRINT"SURPRISE, A POLE WAS FOUND INSTEAD OF A ZERO!" :1430 REM ENDIF :1440 PRINT :1450 RETURN :1460 END Pascal Code procedure FixedPoint({function G(X:real):real;} ::: var Pterm:real; Max:integer; Tol:real; ::: var Pnew:real; var Cond,Kcount:integer); : label 999; : const Big = 1E10; Small = 1E-20; : var Dx,Dg,Pold,RelErr,Slope:real; : begin :: RelErr := 1; :: Pnew := G(Pterm); :: Kcount := 0; :: while ((RelErr>=Tol) and (KCount<=Max)) do : begin :: if Kcount <= 2 then PKcount := Pterm; :: Pold := Pterm; :: Pterm := Pnew; :: Pnew := G(Pterm); :: Dg := Pnew - Pterm; :::: RelErr := ABS(Dg)/(ABS(Pnew)+Small); :: Kcount := Kcount+1; : if (Pnew < -Big) or (Big < Pnew) then goto 999; :: end; : 999: : if Kcount <= 2 then PKcount := Pterm; : if Dg = 0 then :: Slope := 0 : else : begin :: Dx := Pterm - Pold; : if Dx <> 0 then :: Slope := Dg/Dx : else :: Slope := 6.023E23; : end; : if ABS(Slope) < 1 then :: begin :: Cond := 1; : if Slope < 0 then Cond := 2; : end : else : begin :: Cond := 3; : if Slope < 0 then Cond := 4; : end; : if RelErr < Tol then : if (Cond = 3) or (Cond = 4) then Cond := 5; : Kcount := Kcount+1; : end; Source Numerical Methods in Scientific Computing, Volume 1 Module for Fixed Point Iteration 1 Latest activity Category:Browse